package dse.modules;

import java.util.Random;
import java.util.TreeMap;

/**
 * This is mostly adapeter from another students work.
 *  
 * @author Aaron
 */
public class ZipfDistribution {
	private int cardinality;
	private double [] distribution;
	private double [] accumulateDist;
	
	/**
	 * Create this class.
	 * 
	 * Code inspired by: http://en.wikipedia.org/wiki/Zipf%27s_law
	 * 
	 * @param characterizingExponent	Just use 1 (see website above for 
	 * 									explanation).
	 * @param cardinality				Basically, how big of a zipf 
	 * 									distribution we need.
	 */
	public ZipfDistribution (double characterizingExponent, int cardinality) {
		assert cardinality > 0;
		
		this.cardinality = cardinality;
		this.distribution = new double [cardinality];
		this.accumulateDist = new double [cardinality];
		
		double base = 0;
		for (int j = 0; j < cardinality; j++)
			base = base + 1.0 / Math.pow(j+1, characterizingExponent);
		
		for (int j = 0; j < cardinality; j++) {
			distribution[j] = (1.0 / Math.pow(j+1, characterizingExponent)) / 
				base;
		}
		
		accumulateDist[0] = distribution[0];
		for (int j = 1; j < cardinality; j++) {
			accumulateDist[j] = accumulateDist[j - 1] + distribution[j];
		}
	}
	
	public int getCardinatly () { return cardinality; }
	/**
	 * 
	 * @param index		1 based (not 0 based!) index.
	 * @return			
	 */
	public double getDistribution (int index) { return distribution[index-1]; }
	
	/**
	 * Gets the rank (1 based) for the given number between 0 and 1.  This might
	 * be too slow in large distributions... may have to change it to do a 
	 * binary search or something like that. 
	 * 
	 * @param chance
	 * @return
	 */
	public int getRank (double choosenNumber) {
//		for (int a = 0; a < cardinality; a++) {
//			choosenNumber -= distribution[a];
//			if (choosenNumber < 0)
//				return a+1;
//		}
//		return cardinality;
	//binary search
		int l = 0, r = cardinality - 1, mid;
		while (l <= r) {
			mid = (l + r) >> 1;
			if (choosenNumber >= accumulateDist[mid]) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return Math.min(r + 2, cardinality);
	}
	
	
	
	
	/**
	 * For testing :)
	 * 
	 * @param args
	 */
	public static void main (String [] args) {
		ZipfDistribution z = new ZipfDistribution (0.7, 10000);
		
		double sum = 0;
		double max = 0;
		for (int a = 0; a < z.getCardinatly(); a++) {
			if(a < 2)
				System.out.println(""+(a+1)+":\t"+z.getDistribution(a+1));
			sum += z.getDistribution(a+1);
			if(z.getDistribution(a+1) > max)
				max = z.getDistribution(a+1);
		}
		System.out.println("sum (should be 1): "  + sum);
		System.out.println("Max :" + 10000*max);
		
		System.out.println();
		TreeMap<Integer, Integer> set = new TreeMap<Integer, Integer>();
		Random r = new Random ();
		final int choose = 1000;
		for (int a = 0; a < choose; a++) {
			int rank = z.getRank(r.nextDouble());
			if (set.containsKey(rank))
				set.put(rank, set.get(rank) + 1);
			else
				set.put(rank, 1);
		}
		
		/*for (Integer key : set.keySet()) {
			System.out.println(
					"\t" + key + " choosen " + set.get(key) + " times (" +
					(100.0*set.get(key)/choose) + "%)."
					);
		}*/
	}
}




















